SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Triangular array</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Triangular array</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Triangular_matrix" title="Triangular matrix">Triangular matrix</a>.</div>

<p>In mathematics and computing, a <b>triangular array</b> of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the <i>i</i>th row contains only <i>i</i> elements.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>Notable particular examples include these:

</p>

<ul><li>The <a href="Bell_triangle" title="Bell triangle">Bell triangle</a>, whose numbers count the <a href="Partition_of_a_set" title="Partition of a set">partitions of a set</a> in which a given element is the largest <a href="Singleton_(mathematics)" title="Singleton (mathematics)">singleton</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Catalan's_triangle" title="Catalan's triangle">Catalan's triangle</a>, which counts strings of matched parentheses<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Euler's_triangle" class="mw-redirect" title="Euler's triangle">Euler's triangle</a>, which counts permutations with a given number of ascents<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Floyd's_triangle" title="Floyd's triangle">Floyd's triangle</a>, whose entries are all of the integers in order<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Hosoya's_triangle" title="Hosoya's triangle">Hosoya's triangle</a>, based on the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Lozani%C4%87's_triangle" title="Lozanić's triangle">Lozanić's triangle</a>, used in the mathematics of chemical compounds<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Narayana_triangle" class="mw-redirect" title="Narayana triangle">Narayana triangle</a>, counting strings of balanced parentheses with a given number of distinct nestings<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Pascal's_triangle" title="Pascal's triangle">Pascal's triangle</a>, whose entries are the <a href="Binomial_coefficients" class="mw-redirect" title="Binomial coefficients">binomial coefficients</a><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup></li></ul>

<p>Triangular arrays of integers in which each row is symmetric and begins and ends with 1 are sometimes called <b>generalized Pascal triangles</b>; examples include Pascal's triangle, the Narayana numbers, and the triangle of Eulerian numbers.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Generalizations">Generalizations</h2></div>

<p>Triangular arrays may list mathematical values other than numbers; for instance the <a href="Bell_polynomials" title="Bell polynomials">Bell polynomials</a> form a triangular array in which each array entry is a polynomial.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p><p>Arrays in which the length of each row grows as a linear function of the row number (rather than being equal to the row number) have also been considered.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p><a href="Romberg's_method" title="Romberg's method">Romberg's method</a> can be used to estimate the value of a <a href="Definite_integral" class="mw-redirect" title="Definite integral">definite integral</a> by completing the values in a triangle of numbers.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p><p>The <a href="Boustrophedon_transform" title="Boustrophedon transform">Boustrophedon transform</a> uses a triangular array to transform one <a href="Integer_sequence" title="Integer sequence">integer sequence</a> into another.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p><p>In general, a triangular array is used to store any table indexed by two <a href="Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a> where <i>j</i> ≤ <i>i</i>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Indexing">Indexing</h2></div>

<p>Storing a triangular array in a computer requires a mapping from the two-dimensional coordinates (<i>i</i>, <i>j</i>) to a linear <a href="Memory_address" title="Memory address">memory address</a>. If two triangular arrays of equal size are to be stored (such as in <a href="LU_decomposition" title="LU decomposition">LU decomposition</a>), they can be combined into a standard <a href="Array_(data_structure)" title="Array (data structure)">rectangular array</a>. If there is only one array, or it must be easily appended to, the array may be stored where row <i>i</i> begins at the <i>i</i>th <a href="Triangular_number" title="Triangular number">triangular number</a> <i>T<sub>i</sub></i>. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (<code>i*(i+1)/2</code>), so some optimizations such as using a <a href="Multiplication_algorithm#Usage_in_computers" title="Multiplication algorithm">sequence of shifts and adds</a> are not available.

</p>

<ul><li><a href="Triangular_number" title="Triangular number">Triangular number</a>, the number of entries in such an array up to some particular row</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFShallit1980" class="citation cs2"><a href="Jeffrey_Shallit" title="Jeffrey Shallit">Shallit, Jeffrey</a> (1980), <a rel="nofollow" class="external text" href="http://www.fq.math.ca/Books/Collection/shallit.pdf">"A triangle for the Bell numbers"</a> <span class="cs1-format">(PDF)</span>, in Hoggatt, Verner E. Jr.; Bicknell-Johnson, Marjorie (eds.), <a rel="nofollow" class="external text" href="https://www.fq.math.ca/collection.html"><i>A collection of manuscripts related to the Fibonacci sequence</i></a>, Santa Clara, Calif.: Fibonacci Association, pp. <span class="nowrap">69–</span>71, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0624091">0624091</a></cite>.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFKitaevLiese2013" class="citation cs2"><a href="Sergey_Kitaev" title="Sergey Kitaev">Kitaev, Sergey</a>; Liese, Jeffrey (2013), <a rel="nofollow" class="external text" href="https://personal.strath.ac.uk/sergey.kitaev/Papers/mesh1.pdf">"Harmonic numbers, Catalan's triangle and mesh patterns"</a> <span class="cs1-format">(PDF)</span>, <i><a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a></i>, <b>313</b> (14): <span class="nowrap">1515–</span>1531, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1209.6423">1209.6423</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2013.03.017">10.1016/j.disc.2013.03.017</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3047390">3047390</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18248485">18248485</a></cite>.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFVellemanCall1995" class="citation cs2">Velleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", <i>Mathematics Magazine</i>, <b>68</b> (4): <span class="nowrap">243–</span>253, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F0025570X.1995.11996328">10.1080/0025570X.1995.11996328</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2690567">2690567</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1363707">1363707</a></cite>.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFMillerMillerJackson1987" class="citation cs2">Miller, Philip L.; Miller, Lee W.; Jackson, Purvis M. (1987), <i>Programming by design: a first course in structured programming</i>, Wadsworth Pub. Co., pp. <span class="nowrap">211–</span>212, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-534-08244-4</bdi></cite>.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFHosoya1976" class="citation cs2"><a href="Haruo_Hosoya" title="Haruo Hosoya">Hosoya, Haruo</a> (1976), "Fibonacci triangle", <i><a href="The_Fibonacci_Quarterly" class="mw-redirect" title="The Fibonacci Quarterly">The Fibonacci Quarterly</a></i>, <b>14</b> (2): <span class="nowrap">173–</span>178, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F00150517.1976.12430575">10.1080/00150517.1976.12430575</a></cite>.</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFLosanitsch1897" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Sima_Lozani%C4%87" title="Sima Lozanić">Losanitsch, Sima M.</a> (1897), <a rel="nofollow" class="external text" href="https://zenodo.org/record/1425862">"Die Isomerie-Arten bei den Homologen der Paraffin-Reihe"</a> [The isomery species of the homologues of the paraffin series], <i><a href="Chem._Ber." class="mw-redirect" title="Chem. Ber.">Chem. Ber.</a></i> (in German), <b>30</b> (2): <span class="nowrap">1917–</span>1926, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fcber.189703002144">10.1002/cber.189703002144</a></cite>.</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFBarry2011" class="citation cs2">Barry, Paul (2011), <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.pdf">"On a generalization of the Narayana triangle"</a> <span class="cs1-format">(PDF)</span>, <i>Journal of Integer Sequences</i>, <b>14</b> (4) 11.4.5, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2792161">2792161</a></cite>.</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFEdwards2002" class="citation cs2"><a href="A._W._F._Edwards" title="A. W. F. Edwards">Edwards, A. W. F.</a> (2002), <i>Pascal's Arithmetical Triangle: The Story of a Mathematical Idea</i>, JHU Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8018-6946-4</bdi></cite>.</span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFBarry2006" class="citation cs2">Barry, Paul (2006), <a rel="nofollow" class="external text" href="http://www.emis.de/journals/JIS/VOL9/Barry/barry91.pdf">"On integer-sequence-based constructions of generalized Pascal triangles"</a> <span class="cs1-format">(PDF)</span>, <i>Journal of Integer Sequences</i>, <b>9</b> (2) 6.2.4, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2006JIntS...9...24B">2006JIntS...9...24B</a></cite>.</span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFRota_BulòHancockAzizPelillo2012" class="citation cs2">Rota Bulò, Samuel; Hancock, Edwin R.; Aziz, Furqan; Pelillo, Marcello (2012), "Efficient computation of Ihara coefficients using the Bell polynomial recursion", <i>Linear Algebra and Its Applications</i>, <b>436</b> (5): <span class="nowrap">1436–</span>1441, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.laa.2011.08.017">10.1016/j.laa.2011.08.017</a></span>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2890929">2890929</a></cite>.</span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFFielderAlford1991" class="citation cs2">Fielder, Daniel C.; Alford, Cecil O. (1991), "Pascal's triangle: Top gun or just one of the gang?", in Bergum, Gerald E.; Philippou, Andreas N.; Horadam, A. F. (eds.), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=SfWNxl7K9pgC&pg=PA77"><i>Applications of Fibonacci Numbers (Proceedings of the Fourth International Conference on Fibonacci Numbers and Their Applications, Wake Forest University, N.C., U.S.A., July 30–August 3, 1990)</i></a>, Springer, pp. <span class="nowrap">77–</span>90, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780792313090</bdi></cite>.</span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFThacher_Jr.1964" class="citation cs2">Thacher Jr., Henry C. (July 1964), "Remark on Algorithm 60: Romberg integration", <i>Communications of the ACM</i>, <b>7</b> (7): <span class="nowrap">420–</span>421, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F364520.364542">10.1145/364520.364542</a></span>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29898282">29898282</a></cite>.</span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite id="CITEREFMillarSloaneYoung1996" class="citation cs2">Millar, Jessica; Sloane, N. J. A.; Young, Neal E. (1996), "A new operation on sequences: the Boustrouphedon transform", <i>Journal of Combinatorial Theory</i>, Series A, <b>76</b> (1): <span class="nowrap">44–</span>54, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math.CO/0205218">math.CO/0205218</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcta.1996.0087">10.1006/jcta.1996.0087</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15637402">15637402</a></cite>.</span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><span class="citation mathworld" id="Reference-Mathworld-Number_Triangle"><cite id="CITEREFWeisstein" class="citation web cs2"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a>, <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/NumberTriangle.html">"Number Triangle"</a>, <i><a href="MathWorld" title="MathWorld">MathWorld</a></i></cite></span></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-28" href="https://en.wikipedia.org/wiki/?title=Triangular_array&oldid=1292665520">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>